package com.mamingchao.foundation.arraysort.mergesort;

import com.mamingchao.foundation.arraysort.Sortable;

/**
 * 马老师实现的
 * Created by mamingchao on 2021/3/10.
 */
public class MergeSortUpgrade1 implements Sortable{

    /**
     * 2 4 6 1 3 5 6
     * @param mid 是1的位置，右侧数组 第一个值的索引
     * @param right 6.右侧数组最后一个index
     * @param left 2 左侧数组第一个index
     * 对前半段和后半段排好序的数组进行 merge 排序
     * @return
     */
    private static void merge(int[] arr,int left,int mid , int right) {
        int[] newArr = new int[right - left + 1];

        //子数组1 的索引
        int i = left;
        //子数组2 的索引
        int j = mid;
        //新申请的大数组的索引
        int k = 0;

        while (i< mid && j<= right) {
            // 马老师说 如果不加 = ，当i 和j位置的值一样的时候，从后半截数组拿，会把归并变成不稳定
            //这个地方不太清楚，还需要 琢磨琢磨
//            if (array[i] <= array [j]) {
            newArr[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }

        //说明 subArr2 所有的element 都放到新数组里面去了
        while (i < mid) newArr[k++] = arr[i++];

        //说明 subArr1 所有的element 都放到新数组里面去了,subArr2的没全部放完，但剩下的都是大的，直接
        //把剩下的全部拿出来贴到新数组后面
        while (j <= right)
            newArr[k++] = arr[j++];

        for (int l = 0; l < newArr.length; l++) {
            arr[left+l] = newArr[l];
        }

    }

    @Override
    public void sort(int[] arr, int left, int right) {
        if (right < 0 || left < 0 || right < left) {
            throw new RuntimeException("wrong left or right index value!");
        }

        if (right == left) return;


        //计算对半分的中间索引值
        int mid = left + (right-left)/2;

        //左边排好序
        sort(arr,left,mid);
        //右边排好序
        sort(arr,mid+1,right);

        merge(arr,left,mid+1,right);
    }

}


